/**
 * 
 */
package backtrack.passed;

/**
 * @author xyyi
 * 
 */
public class LongestOnesPath {

    public int longestPath(int[][] m) {
	int rows = m.length;
	int cols = m[0].length;
	boolean[][] flag = new boolean[rows][cols];
	int max = 0;
	for (int row = 0; row < rows; row++) {
	    for (int col = 0; col < cols; col++) {
		max = Math.max(max, longestPathRHelper(m, flag, row, col, 0));
	    }
	}

	return max;
    }

    public int longestPathRHelper(int[][] m, boolean[][] flag, int row,
	    int col, int count) {

	int rows = m.length, cols = m[0].length;
	if (row < 0 || row >= rows || col < 0 || col >= cols)
	    return count;
	if (m[row][col] == 0 || flag[row][col] == true)
	    return count;

	// count++;
	flag[row][col] = true;
	int length = count + 1;
	length = Math.max(length,
		longestPathRHelper(m, flag, row, col + 1, count + 1));
	length = Math.max(length,
		longestPathRHelper(m, flag, row + 1, col, count + 1));
	length = Math.max(length,
		longestPathRHelper(m, flag, row, col - 1, count + 1));
	length = Math.max(length,
		longestPathRHelper(m, flag, row - 1, col, count + 1));

	flag[row][col] = false;
	return length;
    }

    /**
	 * 
	 */
    public LongestOnesPath() {
	// TODO Auto-generated constructor stub
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
	int[][] matrix = { { 0, 0, 0, 0, 0, 0, 0 }, { 1, 1, 1, 1, 1, 1, 1 },
		{ 0, 1, 1, 1, 0, 0, 0 } };
	LongestOnesPath lop = new LongestOnesPath();
	System.out.println(lop.longestPath(matrix));
    }

}
